#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <list>
#include <stack>

using namespace std;

struct vertex{
	explicit vertex(char c):ch(c){};
	char ch;
	int dist;
	bool known;
	vertex* pv;
	list<pair<vertex*,unsigned int> > adj_vertex;
};

typedef vector<vertex> Graph;

vertex* find_v(Graph& g, char c){
	for(unsigned int i=0;i<g.size();++i)
		if(g[i].ch == c)
			return &g[i];
	return NULL;
}

void add_edge(Graph& g, char v1,char v2, unsigned int weight){
	find_v(g,v1)->adj_vertex.push_back(make_pair(find_v(g,v2),weight) );
}

vertex* find_unknown_shortest(Graph &g){
	int dist=1000;
	vertex* v=NULL;
	for(Graph::iterator i=g.begin(); i!= g.end(); ++i){
		if(i->known==false){
			if(i->dist!=-1){
				if(i->dist<=dist){
					dist=i->dist;
					v=&(*i);
				}
			}
		}
	}
	return v;
}

void dijkstra(Graph& g, vertex* v){
	for(Graph::iterator i=g.begin(); i!= g.end(); ++i){
		i->dist=-1;
		i->known=false;
	}
	v->dist=0;
	while(1){
		vertex* v = find_unknown_shortest(g);
		if(!v)
			break;
		v->known=true;
		list<pair<vertex*,unsigned int> > & adj = v->adj_vertex;
		for(list<pair<vertex*,unsigned int> > ::iterator j=adj.begin(); j!= adj.end(); ++j){
			vertex* u = j->first;
			unsigned int w = j->second;
			if(u->dist == -1 || u->dist > v->dist + w){
				u->dist = v->dist+w;
				u->pv = v;
			}
		}		
	}
}

void show_path(vertex* v, vertex* u){
	cout<<"path from "<<v->ch<<" to "<<u->ch<<endl;
	stack<char> s;
	while(u!= v){
		s.push(u->ch);
		u=u->pv;
	}
	s.push(v->ch);
	while(! s.empty()){
		cout<<s.top()<<" ";
		s.pop();
	}
	cout<<endl;
}

int main(){
	map<char,string> data;
	data['a']= string("b2c4d5");
	data['b']=string("d7e8");
	data['c'] = string("f1");
	data['d']=string("c2f3g4");
	data['e']=string("d5g9");
	data['f']=string("");
	data['g']=string("f7");

	Graph g;
	map<char,string>::iterator iter;   
	for( iter = data.begin(); iter != data.end(); iter++ ) {
		g.push_back(vertex(iter->first));
	}

	for( iter = data.begin(); iter != data.end(); iter++ ) {
		string str=iter->second;
		for(unsigned int i=0; i<str.size(); i+=2){
			add_edge(g,iter->first,str[i],str[i+1]-'0');
			//		cout<<"adding edge "<<iter->first<<" "<<str[i]<<endl;
		}
	}

	dijkstra(g,&g[0]);
	for(Graph::iterator i=g.begin(); i!= g.end(); ++i){
		cout<<i->ch<<"  "<<i->dist<<endl;
	}
	
	show_path(find_v(g,'a'),find_v(g,'g'));
	return 0;
}
